package medium.滑动窗口;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 2831. 找出最长等值子数组
 * 创建时间：2024-05-23 09:06
 */
public class 找出最长等值子数组_2831 {
    /**
     * 设nums的等值子数组下标 pos[right] 到 pos[left]，在删除元素前，子数组长度为
     *      pos[right] - pos[left] + 1
     * 子数组有
     *      right - left + 1
    *  个元素是相同的，这些元素无需删除，要删除的元素个数为
     *  pos[right] - pos[left] - (right - left)
     *  如果要删除元素个数的值 > k，则不符合要求，需要移动left，直至 <= k，然后使用right - left + 1更新 ans
     *  简化：pos[right] - pos[left] - (right - left) 可以修改为 pos[right] - right - (pos[left] - left)
     */
    static class Solution {
        public int longestEqualSubarray(List<Integer> nums, int k) {
            int size = nums.size();
            List<Integer>[] posList = new ArrayList[size + 1];
            Arrays.setAll(posList, l -> new ArrayList<>());
            for (int i = 0; i < size; i++) {
                Integer x = nums.get(i);
                posList[x].add(i - posList[x].size());
            }
            int ans = 0;
            for (List<Integer> pos : posList) {
                if (ans >= pos.size()) {
                    continue;
                }
                int left = 0;
                for (int right = 0; right < pos.size(); right++) {
                    while (pos.get(right) - pos.get(left) > k) {
                        left++;
                    }
                    ans = Math.max(ans, right - left + 1);
                }
            }
            return ans;
        }
    }
}
